The subject matter of this application is related to U.S. application Ser. No. 09/065,488 filed Apr. 24, 1998, entitled xe2x80x9cMulti-Resolution Graphic Representation Generated By Weight-Controlled Vertex Clustering For Interactive Visualization Applicationsxe2x80x9d assigned to the assignee of this invention, and incorporated herein by reference.
The present invention relates generally to computer graphics and virtual reality. More specifically, the invention relates to systems and methods for generating bounding volume hierarchies for use in the checking of collisions among objects in complex interactive computer environments or in ray tracing computation to generate photo-realistic computer images.
Fast rendering and collision detection are two fundamental goals of many interactive 3D graphics applications. Many realistic-looking 3D models, containing millions of polygons all of which may be visible in a complex scene, cannot be effectively rendered at interactive frame rates. A solution for this problem is to use multi-resolution or level-of-detail modeling, in which each object has a series of geometric approximations with increasingly lower rendering cost, while still resembling the original models from all directions. On the other hand, navigation in a complex scene requires extensive interference detection between models and thus needs support from very efficient collision detection data structures to achieve interactive frame rates.
There is an interest in interactive visualization and manipulation of architectural, mechanical and CAD models in applications such as computer simulation, computer game, object modeling, and virtual prototyping. Such applications may be standalone, distributed or over the world-wide-web. Systems and methods that detect collisions have been described in:
U.S. Pat. No. 5,572,634, xe2x80x9cMethod and Apparatus for Spatial Simulation Accelerationxe2x80x9d issued to Jerome Duluk, Jr., Nov. 5, 1996;
U.S. Pat. No. 5,515,489, xe2x80x9cCollision Detector Utilizing Collision Contoursxe2x80x9d issued to Larry Yaeger, May 7, 1996;
U.S. Pat. No. 4,888,707, xe2x80x9cObject Collision Detection Method and Apparatusxe2x80x9d issued to Kenji Shimada, Dec. 19, 1989;
European Patent No. 780798, xe2x80x9cMethod and Apparatus for Object Identification and Collision Detection in Three Dimensional Graphics Spacexe2x80x9d issued to Devic Goran, Jan. 7, 1998.
Systems and methods for utilizing spherical or voxel models of objects to assist collision detection in specific application areas are described in:
U.S. Pat. No. 5,548,694, xe2x80x9cCollision Avoidance System for Voxel-Based Object Representationxe2x80x9d issued to Sarah Frisken Gibson, Aug. 20, 1996;
U.S. Pat. No. 5,347,459, xe2x80x9cReal Time Collision Detectionxe2x80x9d issued to Michael Greenspan et. al., Sep. 13, 1994;
U.S. Pat. No. 5,056,031, xe2x80x9cApparatus for Detecting the Collision of Moving Objectsxe2x80x9d issued to Masaru Nakano et. al., Oct. 8, 1991.
The above teachings concentrate on the process of collision detection and the applications to specific domains. On the other hand, the present invention is a method for processing an arbitrary collection of objects, in a simulated computer environment, into hierarchies of bounding volumes. The following teachings are most relevant to the present invention:
(1) U.S. Pat. No. 5,613,049, xe2x80x9cMethod for Creating Spatially Balanced Bounding Volume Hierarchies for Use in a Computer Generated Display of a Complex Structurexe2x80x9d issued to Brechner et al., Mar. 18, 1997;
(2) G. Barequet, B. Chazelle, L. Guibas, J. Mitchell and A. Tal, xe2x80x9cBOXTREE:: A Hierarchical Representation for Surfaces in 3Dxe2x80x9d, Proceedings Eurographics ""96, Vol. 15(3), pp. C-387-396, C-484, August 1996;
(3) S. Gottschalk, M. C. Lin and D. Manocha, xe2x80x9cOBBTree:: A Hierarchical Structure for Rapid Interference Detectionxe2x80x9d, Computer Graphics (SIGGRAPH ""96 Proceedings), pp. 171-179, 1996;
(4) J. Klosowski, M. Held, J. Mitchell, H. Sowizral and K. Zikan, xe2x80x9cEfficient Collision Detection Using Bounding Volume Hierarchies of k-DOPsxe2x80x9d, IEEE Transactions on Visualization and Computer Graphics, vol. 4 (1), 1998, pp 21-36.
Although the above documents provide significant advances in constructing good bounding volume hierarchies, there still remains many controversial design issues, such as top-down verses bottom-up construction approaches; choices between the types of bounding volumes, and various splitting rules for building the hierarchies (see, for example, Klosowski et. al.,1998). Some of these choices involve expensive computation. It is not readily apparent which choices are better.
Many popular approaches are based either on the hierarchies of bounding volumes that successively approximate parts of the input model until the exact geometry of the model is reached, or spatial decomposition of the space occupied by the model. Both ideas are aiming to reduce the number of pairs of objects or primitives that need to be checked for contact.
Besides collision detection, bounding volume hierarchies are also utilized to accelerate ray tracing process to generate photo-realistic computer images (see Arvo and Kirk, xe2x80x9cA Survey of Ray Tracing Acceleration Techniquesxe2x80x9d, in An Introduction to Ray Tracing, A. S. Glassner, ed., pp. 201-262, Academic Press, 1990). Relevant teachings include:
(1) J. Goldsmith and J. Salmon, xe2x80x9cAutomatic Creation of Object Hierarchies for Ray Tracingxe2x80x9d, IEEE Computer Graphics and Applications, vol. 7(5), pp.14-20, May 1987;
(2) I. Scherson and E. Caspary, xe2x80x9cData Structures and the Time Complexity of Ray Tracingxe2x80x9d, The Visual Computer, vol. 3, pp. 201-213, 1987 (see Section 5);
(3) A. Glassner, xe2x80x9cSpacetime Ray Tracing for Animationxe2x80x9d, IEEE Computer Graphics and Applications, vol. 8(3), pp. 60-70, March 1988 (see pp. 62-63);
(4) F. Sillion and G. Drettakis, xe2x80x9cFeature-based control of Visibility Error: A Multi-Resolution Clustering Algorithm for Global illuminationxe2x80x9d, Computer Graphics (SIGGRAPH""95 Proceedings), pp. 145-152, August 1995 (see pp. 149);
(5) K. Whang, J. Song, J. Chang, J. Kim, W. Cho, C. Park and 1. Song, xe2x80x9cOctree-R: An Adaptive Octree for Efficient Ray Tracingxe2x80x9d, IEEE Transactions on Visualization and Computer Graphics, vol. 1(4), December 1995;
(6) U.S. Pat. No. 5,613,049, xe2x80x9cMethod for Creating Spatially Balanced Bounding Volume Hierarchies for Use in a Computer Generated Display of a Complex Structurexe2x80x9d issued to Brechner et al., Mar. 18, 1997;
(7) K. Klimaszewski and T. Sederberg, xe2x80x9cFaster Ray Tracing Using Adaptive Gridsxe2x80x9d, IEEE Computer Graphics and Applications, vol. 17(1), pp. 42-51, 1997.
In Kay and Kajiya, xe2x80x9cRay Tracing Complex Scenesxe2x80x9d, Computer Graphics (SIGGRAPH""86 Proceedings), pp. 269-278, August 1986 (see Section 3.1), the authors mentioned several interrelated properties that would seem to distinguish a good hierarchy from a bad one. These include (i) any given sub-tree in the hierarchy should contain objects that are near each other; (ii) the bounding volume of each node should be minimal; (iii) the sum of all bounding volume should be minimal; and (iv) the construction of the tree should concentrate on the nodes nearer the root of the tree. To date, finding close to optimal hierarchy remains a partially solved problem.
It is thus an object of this invention to provide a new system and method to generate effective bounding volume hierarchy. The current invention exploits shape information obtainable from simplified models to partition input model into its natural components so as to generate effective bounding volume hierarchy.
Specifically the inventive method includes first a step of generating simplified models; second, deriving various components of the input model from clues in simplified models; third, joining various components into a hierarchy to form the top few levels of the eventual bounding volume hierarchy; and then finally partitioning parts of each minimal sub-component into the bounding volume hierarchy.
This invention can be used to build a software system or an apparatus that generates effective bounding volume hierarchies for checking collision in interactive computer applications or for ray tracing process to generate photo-realistic images. Such software systems may already have methods to construct simplified models for the same application and, thus, overhead due to simplification needed by the present invention is insignificant. Also, the inventive system is a framework that can incorporate other existing methods within its various embodiments.
This invention may also take the form of an article of manufacture. More specifically, the article of manufacture is a computer-usable medium, including a computer-readable program code embodied therein wherein the computer-readable code causes a computer to execute the inventive method.
Some of the previous teachings have experimental evidence indirectly supporting the effectiveness and efficiency of the current invention. First, the invention is very careful in creating a hierarchy with all necessary considerations mentioned in Kay and Kajiya (1986). In particular, in the handling of the top-most few levels of the hierarchy in that they are a natural partition of the input model. On the whole, the current invention provides a framework that manages input models in a middle-in way to perform bottom-up to find the top few levels of the bounding volume hierarchy and top-down to find the lower levels. The middle-in approach is possible with the partitions derived through simplified models. This two-level structure capitalizes on the best features of both traditional top-down and bottom-up approaches, and can incorporate existing acceleration techniques applicable to both approaches.
Second, a different type of two level structure was suggested by Scherson and Caspary (1987) as their experiments concluded the need of such combined data structure. However, the authors did not provide an efficient computational method to derive such combined data structure. Glassner (1988) is yet another hybrid structure of xe2x80x9cspace subdivision down, bounding volumes upxe2x80x9d embedded together. This structure is different from our distinctive two-level structure, which is also applicable to individual objects and not just a big environment as is intended in Glassner (1988). It is understood that the top few levels of the hierarchy should be effective in guiding the search in the proper branches of the hierarchy as they are involved most of the time in the searching process. The previous teaching of achieving this using spatial subdivision, which is arbitrary regardless of the input model, is replaced in the current invention with component hierarchy which takes input model structure into consideration and thus can better guide searching.
Third, the basic theory given in Goldsmith and Salmon (1987) is exploited, in one embodiment of the invention, in a bottom-up manner in constructing the component hierarchy rather than the top-down manner as originally proposed. This way can better control the merging of sub-components, which is unlike the original faster method in Goldsmith and Salmon (1987) that is sensitive to the insertion order of bounding volumes.
Though slower than top down approach, the current invention is nevertheless efficient as it remains computational inexpensive as there are relatively few components to form a component hierarchy. Traditionally, bottom-up construction (though can better achieve criteria mentioned in Kay and Kajiya, 1986) appears to be more difficult than top-down in that clusters of polygons would have to be defined and grouped locally before they could be put together to form the bounding volume hierarchy. Such difficulty is solved in the current invention using shape information derived from simplified models.
Computationally expensive bottom-up constructions, with the traditional difficulty of clustering polygons mentioned above, are disclosed in Barequet et al. (1996) and U.S. Pat. No. 5,613,049. The former method combines two bounding volumes based on determining the minimum area (volume) among all combinations, whereas the latter on some resulting new bounding volume is no larger than certain predetermined percentage of the old bounding volumes. Another method similar in flavor to these last two methods is given in Sillion and Drettakis (1995). Also, another sophisticated and thus relatively high computational effort is the adaptive grids method disclosed by Klimaszewski and Sederberg (1997).
Fourth, the experiments conducted in using Octree-R by Whang et. al. (1995) concluded that Octree-R is more effective when the objects are non-uniformly distributed than when they are uniformly distributed (pp. 348). Besides extra computational effort, the Octree-R construction algorithm proposed may not find an optimal cutting plane as each axis is considered independently. The current invention can avoid this expensive computation, and is applicable and effective with a simple cutting plane as the data at each sub-component is uniformly distributed, though the whole input model may not be so.
The invention described herein satisfies the above-identified needs in the prior art by providing solutions. The invention provides methods and apparatuses to efficiently generate a good bounding volume hierarchy of an input computer environment to be utilized in collision detection in interactive 3D computer applications, such as computer simulations and computer games, and in ray tracing processes to generate photo-realistic images.
Specifically, the inventive method processes a collection of objects represented by polygons in a computer into a hierarchy of bounding volumes, from a root volume bounding all objects to sub-volumes bounding individual polygons or a small collection of polygons. Many details in the process of generating bounding volume hierarchies can be automated with the present invention and do not require user intervention.
The basic principle employed in this invention uses clues from simplified models to partition a given polygonal model of a complex environment into components, each with a tight bounding volume. Such partitioning can be viewed as a recognition of the shape of the input model, whose essence is captured well by a simplified model. The overall construction has the unique flavor of bottom-up in that polygons of models are distributed into various components, followed by top-down in that polygons within a component are partitioned recursively into smaller parts. This hybrid of top-down and bottom-up adapts itself very well to handle a diverse range of input models that some time favor top-down whereas at other times favor bottom-up.
The process of constructing bounding volume hierarchy is mostly automated, with minimal or no user intervention. Some automatic simplification algorithm is first applied to an input model to derive different level-of-details simplified models. Then, the simplified models are used to derive components, sub-components of components and so on of the input model. Polygons within each sub-component (containing no other sub-component) are further subdivided recursively into small collections of polygons, each with an associated bounding volume. Results of the above can be linked up, in a natural way, into a required bounding volume hierarchy.
Specifically, there is disclosed a method for execution by a data processor that prepares an input model into a bounding volume hierarchy. The framework includes the following steps:
Simplified Model Generation. Various simplified models of an input model are generated. The set of polygons, edges and points in a simplified model shows a sketch of the input model.
Component Derivation. Each simplified model, with polygons, edges and points, can be partitioned into parts that are to be used to guide the partition of the input model into components.
Component Tree Generation. Components and sub-components generated above can be arranged into a tree (such as a binary tree in one embodiment) of component hierarchies, forming the highest levels of the eventual bounding volume hierarchy.
Bounding Volume Hierarchy Generation. Each collection of polygons in each leaf of the component hierarchy is recursively partitioned into smaller collections of polygons and is connected to the component hierarchy into a resulting bounding volume hierarchy. Such bounding volume hierarchy is stored for subsequent use to assist collision detection in 3D interactive applications or ray-tracing processes.